//
//  main.cpp
//  queens
//
//  Created by Xiaoying Wang on 14-7-16.
//  Copyright (c) 2014年 edu.tongji. All rights reserved.
//

#include <iostream>
#include <cstring>

using namespace std;

const int MAXN = 20;

bool col[MAXN];
bool l[2*MAXN];
bool r[2*MAXN];
bool map[MAXN][MAXN];

int n;              //皇后总个数

void output(){                      //输出每种棋盘情况
    if(n >= 13) return;             //可能的情况输出过多，只输出总的数量
    
    cout<<endl;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(map[i][j]) cout<<"Q ";
            else cout<<"* ";
        }
        cout<<endl;
    }
}

int search(int m){  //枚举完m个皇后，可行的方案数
    if(m == n){
        output();
        return 1;
    }
    
    int ans = 0;
    for(int i = 0; i < n; ++i){
        if(!col[i] && !r[m+i] && !l[m-i+n-1]){
            col[i] = r[m+i] = l[m-i+n-1] = map[m][i] = true;
            ans += search(m+1);
            col[i] = r[m+i] = l[m-i+n-1] = map[m][i] = false;
        }
    }
    return ans;
}

int main(int argc, const char * argv[])
{
    cout<<"现有NxN的棋盘，要求放N个皇后，并使任意两个皇后不在同意行，列或斜线上！"<<endl;
    cout<<"建议皇后个数不要选择过大！"<<endl<<endl;;
    
    while(true){
        cout<<"请输入皇后的个数，退出程序请输入q：";
        string command;
        cin>>command;
        
        if('q' == command[0] || 'Q' == command[0]) break;
        n = atoi(command.c_str());
        
        if(n <= 0){
            cout<<endl<<"共有"<<0<<"种解法"<<endl<<endl;
            continue;
        }
        
        if(n >= 20){
            cout<<"数字过大，请输入较小数字！"<<endl;
            continue;
        }
        
        memset(map, false, sizeof(map));
        memset(col, false, sizeof(col));
        memset(l, false, sizeof(l));
        memset(r, false, sizeof(r));
        
        int ans = search(0);
        
        cout<<endl<<"共有"<<ans<<"种解法"<<endl<<endl;
    }

    return 0;
}

